#pragma once
#include <vector>
#include <iostream>
using namespace std;
namespace wanghao
{
    //仿函数 - 小的优先级高,传大于,大的优先级高,传小于
    template<class T>
    struct less
    {
        bool operator()(const T& x,const T& y) const
        {
            return x < y;
        }
    };
    template<class T>
    struct greater
    {
        bool operator()(const T& x,const T& y) const
        {
            return x > y;
        }
    };
    template<class T,class Container = vector<T>,class Compare = less<T>>
    class priority_queue
    {
    public:
        //默认构造
        //priority_queue(){}
        //默认构造我们不写的话编译器会默认生成,但是我们写了编译器不会生成了,所以我们可以强制生成
        priority_queue() = default;//C++11
        //迭代器区间构造
        template <class InputIterator>
        priority_queue (InputIterator first, InputIterator last)
            :_con(first,last)
        {
            //建堆
            for(int i = (_con.size()-1-1)/2;i >= 0;i--)
            {
                AdjustDown(i);
            }
        }
        //向上调整算法
        void AdjustUp(int child)
        {
            Compare com;
            int parent = (child - 1) / 2;
            while(child > 0)
            {
                //if(_con[parent] < _con[child])
                if(com(_con[parent] , _con[child]))
                {
                    swap(_con[child],_con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else break;
            }

        }
        //入数据
        void push(const T& val)
        {
            _con.push_back(val);
            AdjustUp(_con.size()-1);
        }
        //向下调整算法
        void AdjustDown(int parent)
        {
            Compare com;
            int child = parent * 2 + 1;
            while(child < _con.size())
            {
                //if(child + 1 < _con.size() && _con[child] < _con[child + 1])
                if(child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
                {
                    child++;
                }
                //if(_con[parent] < _con[child])
                if(com(_con[parent] , _con[child]))
                {
                    swap(_con[child],_con[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else break;
            }
        }
        //出数据
        void pop()
        {
            swap(_con[0],_con[_con.size()-1]);
            _con.pop_back();
            AdjustDown(0);
        }
        bool empty() const
        {
            return _con.empty();
        }
        const T& top() const
        {
            return _con[0];
        }
        size_t size() const
        {
            return _con.size();
        }
    private:
        Container _con;
    };
}